package random_test;

import java.util.*;


class Node {
    public int val;
    public List<Node> children;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val, List<Node> _children) {
        val = _val;
        children = _children;
    }
}


class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode(int x) {
        val = x;
    }
}


public class Test_0125 {


    //2865. 美丽塔 I
    public long maximumSumOfHeights(List<Integer> maxHeights) {
        int n = maxHeights.size();
        Deque<Integer> stack = new LinkedList<>();
        // 1. 从左往右寻找第一个比当前元素小的元素
        int[] tmp1 = new int[n];
        for(int i = 0; i < n; i++) {
            while(!stack.isEmpty() && maxHeights.get(i) < maxHeights.get(stack.peek())) {
                tmp1[stack.pop()] = i;
            }
            stack.push(i);
        }
        while(!stack.isEmpty()) tmp1[stack.pop()] = -1;

        // 2. 从右往左寻找第一个比当前元素小的元素
        int[] tmp2 = new int[n];
        for(int i = n - 1; i >= 0; i--) {
            while(!stack.isEmpty() && maxHeights.get(i) < maxHeights.get(stack.peek())) {
                tmp2[stack.pop()] = i;
            }
            stack.push(i);
        }
        while(!stack.isEmpty()) tmp2[stack.pop()] = -1;

        // 3. 从 0 ~ n-1 依次求各个美丽山脉的高度
        long ret = 0;
        for(int i = 0; i < n; i++) {
            long sum  = 0;
            for(int j = i; j != -1; ) {
                int index = tmp1[j];
                int count = index == -1? n - j : index - j;
                sum += count * (long)maxHeights.get(j);
                j = index;
            }
            for(int j = i; j != -1; ) {
                int index = tmp2[j];
                int count = index == -1? j + 1 : j - index;
                if(j != i) sum += count * (long)maxHeights.get(j);
                j = index;
            }
            ret = Math.max(ret, sum);
        }
        return ret;
    }


    //2859. 计算 K 置位下标对应元素的和
    public int sumIndicesWithKSetBits(List<Integer> nums, int k) {
        if(k == 0) return nums.get(0);

        int ret = 0, n = nums.size();
        for(int i = (int)(Math.max(2.0, k)) - 1; i < n; i++) {
            if(check(i, k)) ret += nums.get(i);
        }
        return ret;
    }
    public boolean check(int index, int k) {
        int count = 0;
        while(index != 0) {
            count++;
            index = (index) & (index - 1);
        }
        return count == k;
    }

    // 589. N 叉树的前序遍历
    List<Integer> ret;
    public List<Integer> preorder(Node root) {
        ret = new ArrayList<>();
        if(root == null) return ret;

        dfs(root);
        return ret;
    }
    public void dfs(Node root) {
        if(root == null) return;

        ret.add(root.val);
        if(root.children != null) {
            for(Node node : root.children) {
                dfs(node);
            }
        }
    }



    // 590. N 叉树的后序遍历
    List<Integer> ret2;
    public List<Integer> postorder(Node root) {
        ret2 = new ArrayList<>();
        if(root == null) return ret2;

        dfs2(root);
        return ret2;
    }

    public void dfs2(Node root) {
        if(root == null) return;
        if(root.children != null) {
            for(Node node : root.children) {
                dfs(node);
            }
        }
        ret2.add(root.val);
    }



    // 477. 汉明距离总和
    public int totalHammingDistance(int[] nums) {
        int ret = 0, n = nums.length;
        for(int i = 0; i < 30; i++) {
            // 统计第 i 位为1有多少个数
            int count = 0;
            for(int x : nums) {
                count += x>>i&1;
            }
            ret += count * (n - count);
        }
        return ret;
    }


    // 61. 旋转链表
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null || head.next == null || k == 0) return head;

        int count = 0;
        ListNode cur = head;
        for(; cur != null; cur = cur.next) count++;
        k %= count;

        ListNode slow = head, fast = head;
        for(int i = 0; i < k; i++) fast = fast.next;
        while(fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }

        fast.next = head;
        head = slow.next;
        slow.next = null;
        return head;
    }



    // 66. 加一
    public int[] plusOne(int[] digits) {
        int n = digits.length;
        int index = n - 1, carry = 0;

        digits[index] += 1;
        for(; index >= 0 && (digits[index] > 9 || carry != 0); index--) {
            digits[index] += carry;
            carry = digits[index] / 10;
            digits[index] %= 10;
        }

        if(index < 0 && carry > 0) {
            int[] tmp = new int[n + 1];
            tmp[0] = carry;
            for(int i = 0; i < n; i++) tmp[i + 1] = digits[i];
            digits = tmp;
        }
        return digits;
    }



    // LCR 143. 子结构判断
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if(A == null || B == null) return false;
        if(judgeIsSubStructure(A, B)) return true;
        return isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    public boolean judgeIsSubStructure(TreeNode A, TreeNode B) {
        if(A == null && B == null || B == null) return true;
        if(A == null) return false;
        if(A.val != B.val) return false;
        return judgeIsSubStructure(A.left, B.left) && judgeIsSubStructure(A.right, B.right);
    }
}
